package com.lihepeng.leecode.classic.divide_and_conquer;

import org.junit.Test;

import java.util.Arrays;

/**
 * 快排
 */
public class QuickSort {
    /**
     * 寻找某一个元素当做基准元素 一般认为第一个为 基准元素
     * 使用两个索引分别执行数组的开始位置和结束位置
     */
    public void quickSort(int [] arrs) {
        quick(arrs,0,arrs.length-1);
    }
    private void quick(int[]arrs,int left,int right){
        // 终止条件
        if (left>right) {
            return;
        }
        // 基准节点
        int provit = arrs[left];
        int low = left;
        int hight = right;
        while (low < hight) {
            if (provit<=arrs[hight] && low<hight ) {
                hight--;
            }
            arrs[low]=arrs[hight];
            if (provit>=arrs[low] && low<hight) {
                low++;
            }
            arrs[hight] = arrs[low];
        }
        arrs[low] = provit;
        quick(arrs,left,hight-1);
        quick(arrs,hight+1,right);

    }
    // 两个数组元素之间的交换
    private void swap(int[]arrs,int left,int right){
        int temp = arrs[left];
        arrs[left] = arrs[right];
        arrs[right] = temp;
    }
    @Test
    public void runTest() {
        int []arrs = {1,3,6,2,4,9};
        quickSort(arrs);
        System.out.println(Arrays.toString(arrs));
    }
}


